package datastruct.graph;

import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;

/**
 * 用邻接矩阵表示的图
 */
public class MatrixBasedGraph {

    public static void main(String[] args) {
        final int nan = Integer.MAX_VALUE;
//        int[][] adj = {{0,10,nan,nan,5},{nan,0,1,nan,2},{nan,nan,0,4,nan},{7,nan,6,0,nan},{nan,3,9,2,0}};
        int[][] adj = {{0,nan},{nan,0}};
        System.out.println(MatrixBasedGraph.dijstraShortestPath1(adj,0,1));
    }

    int[][] adjcentMatrix;

    public MatrixBasedGraph(int[][] adjcentMatrix){
        this.adjcentMatrix = adjcentMatrix;
    }

    /**
     * dijstra最短路算法
     * @return MAX_VALUE 如果不可达
     */
    public static int dijstraShortestPath(int[][] adjcentMatrix, int source, int dest){
        int n = adjcentMatrix.length;
        //certain和uncertain用于保存已经确定最短路径和尚未确定的点集
        HashSet<Integer> certain = new HashSet<>(), uncertain = new HashSet<>();
        certain.add(source);
        for (int i = 0; i < source; i++) {
            uncertain.add(i);
        }
        for (int i = source+1; i < n; i++) {
            uncertain.add(i);
        }
        //curShortest用于保存目前从source到i的最短路径长度
        int[] curShortest = new int[n];
        //初始化为邻接矩阵中source到所有点的距离
        System.arraycopy(adjcentMatrix[source],0,curShortest,0,adjcentMatrix[source].length);
        //开始动态规划，有可能有些点不可达，导致dest始终无法加入certain，所以需要一个flag查看是不是uncertain中的点距离都为MAX_VALUE
        while (true){
            //找uncertain中所有当前距离最短的加入certain
            // TODO: 2021/8/11 这里复杂度是n
            int nextCertain = -1, pathLen = Integer.MAX_VALUE;
            for(int i:uncertain){
                if(curShortest[i]<pathLen){
                    pathLen = curShortest[i];
                    nextCertain = i;
                }
            }
            //如果找不到下一个可达点，说明dest也是不可达
            if(nextCertain==-1) break;
            //找到了nextCertain，将他加入certain,更新他的最短距离
            uncertain.remove(nextCertain);
            certain.add(nextCertain);
            curShortest[nextCertain] = pathLen;
            //如果当前找到的就是dest，没有必要更新其他值了
            if(dest==nextCertain) break;
            //如果不是dest，更新与nextCertain邻接的其他点的当前最短距离
            // TODO: 2021/8/11 这里复杂度是n
            for (int i:uncertain){
                if(adjcentMatrix[nextCertain][i]!=Integer.MAX_VALUE){ //判断邻接
                    int maybeShorter = adjcentMatrix[nextCertain][i]+curShortest[nextCertain];
                    if(maybeShorter<curShortest[i]) curShortest[i] = maybeShorter;
                }
            }
        }
        return curShortest[dest];
    }

    public static int dijstraShortestPath1(int[][] adjcentMatrix, int source, int dest){
        int n = adjcentMatrix.length;
        //certain和uncertain用于保存已经确定最短路径和尚未确定的点集
        HashMap<Integer,Integer> certain = new HashMap<>();
        certain.put(source,0);
        //为方便取uncertain中当前路径最短者，用堆来保存这些点，int[0]表示点编号，int[1]表示到source的当前最短距离
        PriorityQueue<int[]> uncertain = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        for (int i = 0; i < n; i++) {
            if(i==source) continue;
            uncertain.offer(new int[]{i,adjcentMatrix[source][i]});
        }
        while (true){
            //找uncertain中所有当前距离最短的加入certain
            // TODO: 2021/8/11 这里复杂度是logn
            int[] nextCertain = uncertain.poll();
            //找到了nextCertain，将他加入certain
            certain.put(nextCertain[0],nextCertain[1]);
            //如果uncertain中最短路径是max，说明已经没有可达点
            if(nextCertain[1]==Integer.MAX_VALUE) break;
            //如果当前找到的就是dest，没有必要更新其他值了
            if(dest==nextCertain[0]) return nextCertain[1];
            //如果不是dest，更新uncertain中与nextCertain邻接的其他点的当前最短距离
            // TODO: 2021/8/11 这里复杂度是nlogn
            for (Object unt:uncertain.toArray()){
                int[] un = (int[]) unt;
                if(adjcentMatrix[nextCertain[0]][un[0]]!=Integer.MAX_VALUE){ //判断邻接
                    int maybeShorter = adjcentMatrix[nextCertain[0]][un[0]]+nextCertain[1];
                    if(maybeShorter<un[1]){ //走nextCertain[0]使source到un[0]的距离变得更短
                        uncertain.remove(un); //为了触发优先队列重排序，需要先移出再加入
                        un[1] = maybeShorter;
                        uncertain.offer(un);
                    }
                }
            }
        }
        return Integer.MAX_VALUE;
    }


}
